package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.LinkedList;
import java.util.Objects;

public class SymmetricTree {

    /**
     * 递归
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null){
            return true;
        }
        if (left == null || right == null){
            return false;
        }
        return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(right.left, left.right);
    }

    /**
     * 迭代
     * 镜像树的先序遍历和后续遍历的值应该一样
     */
    public boolean isSymmetric1(TreeNode root) {
        TreeNode pre = root, post = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<TreeNode> postStack = new LinkedList<>();
        while (!stack.isEmpty() || pre != null || post != null){
            while (pre != null){
                postStack.push(pre);
                pre = pre.left;
            }
            while (post != null){
                stack.push(post);
                post = post.right;
            }
            if (stack.isEmpty() || postStack.isEmpty()){
                return false;
            }
            pre = stack.pop();
            post = postStack.pop();
            if (pre.val != post.val){
                return false;
            }
            pre = pre.right;
            post = post.left;
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(1,2,2,3,null,null,3);
        PrintUtils.println(root);
        boolean symmetric = new SymmetricTree().isSymmetric1(root);
        System.out.println(symmetric);
    }
}
